"""
用暴力法解决旅行商问题。
作者：ipid （ https://github.com/ipid ）
"""

from itertools import permutations
from typing import List, Optional, Tuple

from tsp_common_code import read_graph, AdjacencyMatrix


class Solution:
    graph: AdjacencyMatrix

    def __init__(self, graph: AdjacencyMatrix):
        self.graph = graph

    def solve(self) -> Tuple[int, List[int]]:
        best_dist: Optional[int] = None
        best_route: List[int] = []

        city_num = len(self.graph)
        for route in permutations(range(1, city_num)):
            last_city = 0
            dist = 0

            for city in route:
                dist += self.graph[last_city][city]
                last_city = city

            dist += self.graph[last_city][0]

            current_route = [0, *route, 0]
            print(f'当前路线：{current_route}，总长度：{dist}')

            if best_dist is None or dist < best_dist:
                best_dist = dist
                best_route = current_route

        return best_dist, best_route


def main():
    graph = read_graph()
    if len(graph) <= 1:
        result_dist, result_route = 0, []
    else:
        result_dist, result_route = Solution(graph).solve()

    print(f'\n最佳路线：{result_route}\n最佳路线总长度：{result_dist}\n')


if __name__ == '__main__':
    main()
